811E - Vladik and Entertaining Flags - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long
#define MAXN 15
#define MAXM 100010
using namespace std;
ll n,m,a[MAXN][MAXM],sz,ind=1;
struct element
{
    ll col[2][MAXN]={0},cnt=0,root[2][MAXN]={0};
};
element neutral_element;
element Merge(element x,element y)
{
    if (!x.col[0][1])
        return y;
    if (!y.col[0][1])
        return x;
    element ans;
    ans.cnt=x.cnt+y.cnt;
    for (ll i=1;i<=n;i++)
    {
        if (x.col[1][i]==y.col[0][i])
        {
            if (x.root[1][i]==y.root[0][i])
                continue;
            ans.cnt--;
            ll val=min(x.root[1][i],y.root[0][i]),prev=max(x.root[1][i],y.root[0][i]);
            for (ll j=1;j<=n;j++)
            {
                if (x.root[0][j]==prev)
                    x.root[0][j]=val;
                if (x.root[1][j]==prev)
                    x.root[1][j]=val;
                if (y.root[0][j]==prev)
                    y.root[0][j]=val;
                if (y.root[1][j]==prev)
                    y.root[1][j]=val;
            }
        }
    }
    for (ll i=1;i<=n;i++)
    {
        ans.col[0][i]=x.col[0][i];
        ans.root[0][i]=x.root[0][i];
        ans.col[1][i]=y.col[1][i];
        ans.root[1][i]=y.root[1][i];
    }
    return ans;
}
struct seg_tree
{
    vector<element> st;
    void Init()
    {
        sz=1;
        while (sz<m)
            sz <<= 1;
        st.resize(2*sz+2);
    }
    void Build()
    {
        for (ll i=sz;i<sz+m;i++)
        {
            ll num=0;
            for (ll j=1;j<=n;j++)
            {
                if (a[j][i-sz+1]==a[j-1][i-sz+1])
                    st[i].root[0][j]=st[i].root[1][j]=st[i].root[0][j-1];
                else
                {
                    st[i].root[0][j]=st[i].root[1][j]=ind++;
                    num++;
                }
                st[i].col[0][j]=st[i].col[1][j]=a[j][i-sz+1];
            }
            st[i].cnt=num;
        }
        for (ll i=sz-1;i>0;i--)
            st[i]=Merge(st[2*i],st[2*i+1]);
    }
    element Calc(ll l,ll r,ll x,ll lx,ll rx)
    {
        if (lx>r || rx<l)
            return neutral_element;
        if (lx>=l && rx<=r)
            return st[x];
        ll mid=(lx+rx)/2;
        return Merge(Calc(l,r,2*x,lx,mid),Calc(l,r,2*x+1,mid+1,rx));
    }
};
seg_tree S;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll q,l,r;
    cin >> n >> m >> q;
    for (ll i=1;i<=n;i++)
    {
        for (ll j=1;j<=m;j++)
            cin >> a[i][j];
    }
    S.Init();
    S.Build();
    while (q--)
    {
        cin >> l >> r;
        cout << S.Calc(l,r,1,1,sz).cnt << "\n";
    }
    return 0;
}